package solution;

import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.Queue;
import java.util.Set;
import java.util.Vector;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import jigsaw.Jigsaw;
import jigsaw.JigsawNode;


/**
 * 在此类中填充算法，完成重拼图游戏（N-数码问题）
 */
public class Solution extends Jigsaw {

    /**
     * 
     * 拼图构造函数
     */
	private List<JigsawNode> solution;
	private Set<JigsawNode> visited;
	private int num;
    public Solution() {
    }

    /**
     * 拼图构造函数
     * @param bNode - 初始状态节点
     * @param eNode - 目标状态节点
     */
    public Solution(JigsawNode bNode, JigsawNode eNode) {
        super(bNode, eNode);
    }

    /**
     *（实验一）广度优先搜索算法，求指定5*5拼图（24-数码问题）的最优解
     * 填充此函数，可在Solution类中添加其他函数，属性
     * @param bNode - 初始状态节点
     * @param eNode - 目标状态节点
     * @return 搜索成功时为true,失败为false
     */
    public boolean BFSearch(JigsawNode bNode, JigsawNode eNode) {
        this.visited = new HashSet<JigsawNode>(1000);
        //open队列用于存放未被访问的节点
        Queue<JigsawNode> open = new LinkedList<JigsawNode>();

        this.beginJNode = new JigsawNode(bNode);
        this.endJNode = new JigsawNode(eNode);
        this.currentJNode = null;

        final int MAX_NODE_NUM = 29000;
        final int DIRS = 4;

        this.num = 0;
        this.solution = null;
        //首先将起始节点加入open队列并标记为已访问
        this.visited.add(this.beginJNode);
        open.add(this.beginJNode);
        //遍历open队列
        while (this.num < MAX_NODE_NUM && !open.isEmpty()) {
            this.num++;
            //遍历下一个点找到目标点就停止
            this.currentJNode = open.poll();
            if (this.currentJNode.equals(eNode)) {
                this.getPath();
                break;
            }
            //next数组用于存放目前node的四个方向
            JigsawNode[] next = new JigsawNode[]{
                    new JigsawNode(this.currentJNode), new JigsawNode(this.currentJNode),
                    new JigsawNode(this.currentJNode), new JigsawNode(this.currentJNode)
            };
            //遍历四个方向，如果已经被访问则跳过，否则标记为已访问并加入open
            for (int i = 0; i < DIRS; i++) {
                if (next[i].move(i) && !this.visited.contains(next[i])) {
                    open.add(next[i]);
                    this.visited.add(next[i]);
                }
            }
        }

        System.out.println("Result:");
        System.out.println("Begin state:" + this.getBeginJNode().toString());
        System.out.println("End state:" + this.getEndJNode().toString());
        System.out.println("Solution Path: ");
        System.out.println(this.getSolutionPath());
        System.out.println("Total number of searched nodes:" + this.num);
        System.out.println("Depth of the current node is:" + this.getCurrentJNode().getNodeDepth());

        return this.isCompleted();
    }


    /**
     *（Demo+实验二）计算并修改状态节点jNode的代价估计值:f(n)
     * 如 f(n) = s(n). s(n)代表后续节点不正确的数码个数
     * 此函数会改变该节点的estimatedValue属性值
     * 修改此函数，可在Solution类中添加其他函数，属性
     * @param jNode - 要计算代价估计值的节点
     */
    public void estimateValue(JigsawNode jNode) {
        
        int s = 0; // 后续节点不正确的数码个数
        int dimension = JigsawNode.getDimension();
        for (int index = 1; index < dimension * dimension; index++) {
            if (jNode.getNodesState()[index] + 1 != jNode.getNodesState()[index + 1]) {
                s++;
            }
        }            
        
        //曼哈顿距离,经常被推荐使用
        int curStartDis = 0;
        int curTargetDis = 0;
        
        // 计算currentNode和targetNode的距离
        for(int i = 1; i < dimension * dimension; i++) {
        	for(int j = 1; j < dimension * dimension; j++) {
        		// current Node
        		int curNode = jNode.getNodesState()[i];
        		int targetNode = endJNode.getNodesState()[j];
        		
        		if(curNode == targetNode && curNode != 0) {
        	
        			//currentNode的坐标（X,Y）
        			int curX = (i - 1) / dimension;
        			int curY = (i + 4) % dimension;
        			        			
        			//targetNode的坐标（X,Y）
        			int targetX = (j - 1) / dimension;
        			int targetY = (j + 4) % dimension;
        			
        			int dX = Math.abs(targetX - curX);
        			int dY = Math.abs(targetY - curY);
        			
        			curTargetDis += (dX + dY);

        			break;
        		}        		
        	}
        }
        
        // 计算currentNode和startNode的距离
        for(int i = 1; i < dimension * dimension; i++) {
        	for(int j = 1; j < dimension * dimension; j++) {
        		// current Node
        		int curNode = jNode.getNodesState()[i];
        		int startNode = beginJNode.getNodesState()[j];
        		
        		if (curNode == startNode && curNode != 0) {
        			//currentNode的坐标（X,Y）
        			int curX = (i - 1) / dimension;
        			int curY = (i + 4) % dimension;
        			        			
        			//startNode的坐标（X,Y）
        			int startX = (j - 1) / dimension;
        			int startY = (j + 4) % dimension;
        			
        			int dX = Math.abs(startX - curX);
        			int dY = Math.abs(startY - curY);
        			
        			curStartDis += (dX + dY);
 
        			break;
				}
        	}
        }
        

        

        //计算价值函数
        int estimate = curTargetDis * 2 + s + curStartDis ;
        
        //RunnerDemo的测试函数
        //jNode.setEstimatedValue(s);
        jNode.setEstimatedValue(estimate);        
    }
}
